/* 小根堆 */
class MinHead {
	constructor() {
		this.heap = [];
	}

	/**
	 * 交换heap两个元素
	 * @param {*} index1
	 * @param {*} index2
	 */
	swap(index1, index2) {
		let temp = this.heap[index1];
		this.heap[index1] = this.heap[index2];
		this.heap[index2] = temp;
	}

	/**
	 * 获取父节点的索引
	 * @param {*} index
	 * @returns
	 */
	getParentIndex(index) {
		// 固定公式
		return (index - 1) >> 1;
	}

	/**
	 * 上移操作, 每次插入要保证堆的正确性
	 * @param {*} index
	 * @returns
	 */
	shiftUp(index) {
		if (index === 0) return;
		// 跟父级比较, 如果小于父级, 应该替换, 坐到父级的位置
		const parentIndex = this.getParentIndex(index);
		if (this.heap[parentIndex] > this.heap[index]) {
			// 交换位置
			this.swap(parentIndex, index);
			this.shiftUp(parentIndex);
		}
	}

	/**
	 * 插入元素
	 * @param {*} value
	 */
	insert(value) {
		this.heap.push(value);
		this.shiftUp(this.heap.length - 1); // 上移操作, 构建小根堆
	}

	/**
	 * 获取左侧节点的索引
	 * @param {*} index
	 */
	getLeftIndex(index) {
		return index * 2 + 1;
	}

	/**
	 * 获取右侧节点的索引
	 * @param {*} index
	 */
	getRightIndex(index) {
		return index * 2 + 2;
	}

	/**
	 * 下移操作
	 * @param {*} index
	 */
	shiftDown(index) {
		const leftIndex = this.getLeftIndex(index);
		const rightIndex = this.getRightIndex(index);

		if (this.heap[index] > this.heap[leftIndex]) {
			this.swap(index, leftIndex);
			this.shiftDown(leftIndex);
		}
		if (this.heap[index] > this.heap[rightIndex]) {
			this.swap(index, rightIndex);
			this.shiftDown(rightIndex);
		}
	}

	/**
	 * 删除堆顶
	 */
	pop() {
		// 不直接删除数组的第一个元素, 是因为会损坏堆结构
		// 而是用最后一个元素替换堆顶, 然后执行"下移"操作
		this.heap[0] = this.heap.pop();
		this.shiftDown(0); // 下移操作
	}

	/**
	 * 获取堆顶
	 * @returns
	 */
	peek() {
		return this.heap[0];
	}

	/**
	 * 获取堆的大小
	 * @returns
	 */
	size() {
		return this.heap.length;
	}
}

/**
 * 四个功能
 * 插入操作
 * 删除堆顶操作
 * 获取堆顶元素
 * 获取对的大小
 */

const h = new MinHead();

h.insert(3);
h.insert(2);
h.insert(1);

h.pop();
